\subsection{The Class PPAD}
The fractional games discussed in this chapter are all \PPAD-complete, as we prove in later sections. The class
\PPAD\ (\emph{\textbf{P}olynomial \textbf{P}arity \textbf{A}rgument in
  a \textbf{D}irected graph}) was introduced by Papadimitriou in
\cite{Papadimitriou94}, which defined a number of syntactic classes in
the semantic class \TFNP, or the set of all total search problems.
% SHORT VERSION - combining paragraphs
A search problem $\mathcal{S}$ consists of a set of inputs
$I_{\mathcal{S}} \subseteq \Sigma^*$ such that for each $x \in
I_{\mathcal{S}}$ there is an associated set of solutions
${\mathcal{S}}_x \subseteq \Sigma^{{|x|}^k}$ for some integer $k$. For
each $x \in I_{\mathcal{S}}$ and $y \in \Sigma^{{|x|}^k}$, it is
decidable in polynomial time whether or not $y$ is in
${\mathcal{S}}_x$. A search problem is {\em{total}} if
${\mathcal{S}}_x \neq \emptyset$ for all $x \in
I_{\mathcal{S}}$. \TFNP\ is the set of all total search problems
\cite{MegiddoPapadimitriou}. \junk{Since TFNP is a semantic class,
  several syntactic classes (e,g., PLS \cite{JohnsonPY}, PPA, PPAD,
  PPP, PPM \cite{Papadimitriou94}) were defined to study the
  computational phenomenon of TFNP.} Since every member of \TFNP\ is
equipped with a mathematical proof that it belongs to \TFNP, a number
of syntactic classes can be defined based on their proof styles. The
complexity class \PPAD\ is the class of all search problems whose
totality is proved using a directed parity argument.

Problems in \PPAD\ are reducible to the \eol\
problem. In \eol, we are given a finite directed
graph in which each node has at most one outgoing edge and at most one
incoming edge. The input to the problem is not a complete list of the
nodes and edges; such a list may be exponentially large in the size of
the input.  Instead, we are given an initial source node and a
circuit. The circuit takes a node name as input and in polynomial time
returns the {\em next}\/ node (the other end of the outgoing edge from
the input node) and the {\em previous}\/ node (the other end of the
incoming edge into the input node). If the input node is a source (or
sink), null is returned as the previous (or next) node. The problem
for \eol\ is to find a sink or a source other than
the initial source.

\junk{ Previous work fills \PPAD\ with discrete versions of fixed
  point problems plus problems related to finding mixed Nash
  equilibria in games. Here, we add to \PPAD\ a series of problems
  concerned with finding pure Nash equilibria in various fractional
  games or with finding stable solution points in problems with
  fractional domains. Some of these new problems are very simple to
  describe and may help to quickly add additional problems to
  \PPAD\ in the future.  } 

\junk{
\begin{framed}
\noindent {\sc{End Of The Line}} : Given two boolean circuits $S$ and $P$ with $n$ input bits and $n$ output bits, such that $P(0^n) = 0^n \neq S(0^n)$, find an input $x \in \{0,1\}^n$ such that $P(S(x)) \neq x$ or $S(P(x)) \neq x \neq 0^n$.
\end{framed}

A polynomially computable function $f$ is a polynomial-time reduction from total search problem
$\mathcal{S}$ to total search problem $\mathcal{T}$ if for every input $x$ of $\mathcal{S}$, $f(x)$ is an input of $\mathcal{T}$, and furthermore there is another polynomial function $g$ such that for every $y \in \mathcal{T}_{f(x)}, g(y) \in \mathcal{S}_x$. A search problem $\mathcal{S}$ in PPAD is called {\bf{PPAD}}-{\em{complete}} if all problems in PPAD reduce to it in polynomial-time.
}